A Comprehensive Survey of Neighborhood%2Dbased Recommendation Methods.

A Novel Approach to Compute Similarities and Its Application to Item Recommendation.

Toptmh Topology Predictor for transmembrane alpha%2Dhelices.

Within%2DNetwork Classification Using Local Structure Similarity.

A Kernel Framework for Protein Residue Annotation.

The Set Classification Problem and Solution Methods.

Document Clustering.
This paper presents the results of an experimental study of some common document clustering techniques: agglomerative hierarchical clustering and K-means. (We used both a “standard” K-means algorithm and a “bisecting ” K-means algorithm.) Our results indicate that the bisecting K-means technique is better than the standard K-means approach and (somewhat surprisingly) as good or better than the hierarchical approaches that we tested.
svmPRAT SVM%2Dbased Protein Residue Annotation Toolkit.

LIBRUS combined machine learning and homology information for sequence%2Dbased ligand%2Dbinding residue prediction.

CONTOUR an efficient algorithm for discovering discriminating subsequences.

CONTOUR an efficient algorithm for discovering discriminating subsequences.

fRMSDAlign Protein Sequence Alignment Using Predicted Local Structure Information for Pairs with Low Sequence Identity.
As the sequence identity between a pair of proteins decreases, alignment strategies that are based on sequence and/or sequence profiles become progressively less effective in identifying the correct structural correspondence between residue pairs. This significantly reduces the ability of comparative modelingbased approaches to build accurate structural models. Incorporating into the alignment process predicted information about the local structure of the protein holds the promise of significantly improving the alignment quality of distant proteins. This paper studies the impact on the alignment quality of a new class of predicted local structural features that measure how well fixed-length backbone fragments centered around each residue-pair align with each other. It presents a comprehensive experimental evaluation comparing these new features against existing state-of-the-art approaches utilizing profile-based and predicted secondary-structure information. It shows that for protein pairs with low sequence similarity (less than 12% sequence identity) the new structural features alone or in conjunction with profile-based information lead to alignments that are considerably better than those obtained by previous schemes. 1.
Genome Alignments Using MPI%2DLAGAN.

TOPTMH Topology Predictor for Transmembrane alpha%2DHelices.

Architecture Aware Partitioning Algorithms.
Existing partitioning algorithms provide limited support for load balancing simulations that are performed on heterogeneous parallel computing platforms. On such architectures, effective load balancing can only be achieved if the graph is distributed so that it properly takes into account the available resources (CPU speed, network bandwidth). With heterogeneous technologies becoming more popular, the need for suitable graph partitioning algorithms is critical. We developed such algorithms that can address the partitioning requirements of scientific computations, and can correctly model the architectural characteristics of emerging hardware platforms.
The Set Classification Problem and Solution Methods.

An Analysis of Information Content Present in Protein%2DDNA Interactions.
Understanding the role proteins play in regulating DNA replication is essential to forming a complete picture of how the genome manifests itself. In this work, we examine the feasibility of predicting the residues of a protein essential to binding by analyzing protein-DNA interactions from an information theoretic perspective. Through the lens of mutual information, we explore which properties of protein sequence and structure are most useful in determining binding residues with a particular focus on sequence features. We find that the quantity of information carried in most features is small with respect to DNA-contacting residues, the bulk being provided by sequence features along with a select few structural features. Supplemental information for this article is available at
Comparison of descriptor spaces for chemical compound retrieval and classification.
Abstract. In recent years the development of computational techniques that build models to correctly assign chemical compounds to various classes or to retrieve potential drug-like compounds has been an active area of research. Many of the bestperforming techniques for these tasks utilize a descriptor-based representation of the compound that captures various aspects of the underlying molecular graph’s topology. In this paper we compare five different set of descriptors that are currently used for chemical compound classification. We also introduce four different descriptors derived from all connected fragments present in the molecular graphs primarily for the purpose of comparing them to the currently used descriptor spaces and analyzing what properties of descriptor spaces are helpful in providing effective representation for molecular graphs. In addition, we introduce an extension to existing vector-based kernel functions to take into account the length of the fragments present in the descriptors. We experimentally evaluate the performance of the previously introduced and the new descriptors in the context of SVM-based classification and ranked-retrieval on 28 classification and retrieval problems derived from 18 datasets. Our experiments show that for both of these tasks, two of the four descriptors introduced in this paper along with the extended connectivity fingerprint based descriptors consistently and statistically outperform previously developed schemes based on the widely used fingerprint- and Maccs keys-based descriptors, as well as recently introduced descriptors obtained by mining and analyzing the structure of the molecular graphs.
Learning preferences of new users in recommender systems an information theoretic approach.

Introduction to special issue on bioinformatics.

A Multi%2DLevel Parallel Implementation of a Program for Finding Frequent Patterns in a Large Sparse Graph.

Discriminating Subsequence Discovery for Sequence Clustering.

Out%2Dof%2Dcore coherent closed quasi%2Dclique mining from large dense graph databases.

Data Mining in Bioinformatics %28BIOKDD%29.

Incremental window%2Dbased protein sequence alignment algorithms.
Motivation: Protein sequence alignment plays a critical role in computational biology as it is an integral part in many analysis tasks designed to solve problems in comparative genomics, structure and function prediction, and homology modeling. Methods: We have developed novel sequence alignment algorithms that compute the alignment between a pair of sequences based on short fixed- or variable-length high-scoring subsequences. Our algorithms build the alignments by repeatedly selecting the highest scoring pairs of subsequences and using them to construct small portions of the final alignment. We utilize PSI-BLAST generated sequence profiles and employ a profile-to-profile scoring scheme derived from PICASSO. Results: We evaluated the performance of the computed alignments on two recently published benchmark datasets and compared them against the alignments computed by existing state-of-the-art dynamic programming-based profile-to-profile local and global sequence alignment algorithms. Our results show that the new algorithms achieve alignments that are comparable or better to those achieved by existing algorithms. Moreover, our results also showed that these algorithms can be used to provide better information as to which of the aligned positions are more reliable—a critical piece of information for comparative modeling applications. Suppl. Data
Discovering frequent geometric subgraphs.
As data mining techniques are being increasingly applied to non-traditional domains, existing approaches  for finding frequent itemsets cannot be used as they cannot model the requirement of these  domains. An alternate way of modeling the objects in these data sets, is to use a graph to model the  database objects. Within that model, the problem of finding frequent patterns becomes that of discovering  subgraphs that occur frequently over the entire set of graphs. In this paper we present a computationally  e#cient algorithm for finding frequent geometric subgraphs in a large collection of geometric graphs. Our  algorithm is able to discover geometric subgraphs that can be rotation, scaling and translation invariant,  and it can accommodate inherent errors on the coordinates of the vertices. We evaluated the performance  of the algorithm using a large database of over 20,000 real two dimensional chemical structures,  and our experimental results show that our algorithms requires relatively little time, can accommodate  low support values, and scales linearly on the number of transactions.
Effective Optimization Algorithms for Fragment%2DAssembly Based protein Structure Prediction.
Despite recent developments in protein structure prediction, an accurate new fold prediction algorithm remains elusive. One of the challenges facing current techniques is the size and complexity of the space containing possible structures for a query sequence. Traditionally, to explore this space fragment assembly approaches to new fold prediction have used stochastic optimization techniques. Here we examine deterministic algorithms for optimizing scoring functions in protein structure prediction. Two previously unused techniques are applied to the problem, called the Greedy algorithm and the Hill-climbing algorithm. The main difference between the two is that the latter implements a technique to overcome local minima. Experiments on a diverse set of 276 proteins show that the Hill-climbing algorithms consistently outperform existing approaches based on Simulated Annealing optimization (a traditional stochastic technique) in optimizing the root mean squared deviation (RMSD) between native and working structures. 1.
Clustering methodologies for identifying country core competencies.

Clustering methodologies for identifying country core competencies.

Comparison of Descriptor Spaces for Chemical Compound Retrieval and Classification.
Abstract. In recent years the development of computational techniques that build models to correctly assign chemical compounds to various classes or to retrieve potential drug-like compounds has been an active area of research. Many of the bestperforming techniques for these tasks utilize a descriptor-based representation of the compound that captures various aspects of the underlying molecular graph’s topology. In this paper we compare five different set of descriptors that are currently used for chemical compound classification. We also introduce four different descriptors derived from all connected fragments present in the molecular graphs primarily for the purpose of comparing them to the currently used descriptor spaces and analyzing what properties of descriptor spaces are helpful in providing effective representation for molecular graphs. In addition, we introduce an extension to existing vector-based kernel functions to take into account the length of the fragments present in the descriptors. We experimentally evaluate the performance of the previously introduced and the new descriptors in the context of SVM-based classification and ranked-retrieval on 28 classification and retrieval problems derived from 18 datasets. Our experiments show that for both of these tasks, two of the four descriptors introduced in this paper along with the extended connectivity fingerprint based descriptors consistently and statistically outperform previously developed schemes based on the widely used fingerprint- and Maccs keys-based descriptors, as well as recently introduced descriptors obtained by mining and analyzing the structure of the molecular graphs.
Multilevel algorithms for partitioning power%2Dlaw graphs.
Graph partitioning is an enabling technology for parallel processing as it allows for the effective decomposition of unstructured computations whose data dependencies correspond to a large sparse and irregular graph. Even though the problem of computing high-quality partitionings of graphs arising in scientific computations is to a large extent wellunderstood, this is far from being true for emerging HPC applications whose underlying computation involves graphs whose degree distribution follows a power-law curve. This paper presents new multilevel graph partitioning algorithms that are specifically designed for partitioning such graphs. It presents new clustering-based coarsening schemes that identify and collapse together groups of vertices that are highly connected. An experimental evaluation of these schemes on 10 different graphs show that the proposed algorithms consistently and significantly
Coherent closed quasi%2Dclique discovery from large dense graph databases.
Frequent coherent subgraphscan provide valuable knowledge about the underlying internal structure of a graph database, and mining frequently occurring coherent subgraphs from large dense graph databaseshas been witnessed several applications and received considerable attention in the graph mining community recently. In this paper, we study how to efficiently mine the complete set of coherent closed quasi-cliques from large dense graph databases, which is an especially challenging task due to the downward-closure property no longer holds. By fully exploring some properties of quasicliques, we propose several novel optimization techniques, which can prune the unpromising and redundant sub-search spaces effectively. Meanwhile, we devise an efficient closure checking scheme to facilitate the discovery of only closed quasi-cliques. We also develop a coherent closed quasi-clique mining algorithm, Cocain 1. Thorough performance study shows that Cocain is very efficient and scalable for large dense graph databases.
Towards a Scalable k NN CF Algorithm Exploring Effective Applications of Clustering.
 Collaborative Filtering (CF)-based recommender systems bring mutual benefits to both users and the operators of the sites with too much information. Users benefit as they are able to find items of interest from an unmanageable number of available items. On the other hand, e-commerce sites that employ recommender systems can increase sales revenue in at least two ways: a) by drawing customers&#039; attention to items that they are likely to buy, and b) by cross-selling items. However, the sheer number of customers and items typical in e-commerce systems demand specially designed CF algorithms that can gracefully cope with the vast size of the data. Many algorithms proposed thus far, where the principal concern is recommendation quality, may be too expensive to operate in a large-scale system. We propose ClustKnn, a simple and intuitive algorithm that is well suited for large data sets. The method first compresses data tremendously by building a straightforward but efficient clustering model. Recommendations are then generated quickly by using a simple Nearest Neighbor-based approach. We demonstrate the feasibility of ClustKnn both analytically and empirically. We also show, by comparing with a number of other popular CF algorithms that, apart from being highly scalable and intuitive, ClustKnn provides very good recommendation accuracy as well.  
Building multiclass classifiers for remote homology detection and fold recognition.

On Mining Instance%2DCentric Classification Rules.

Multiobjective hypergraph%2Dpartitioning algorithms for cut and maximum subdomain%2Ddegree minimization.
Abstract — In this paper we present a family of multi-objective hypergraph partitioning algorithms based on the multilevel paradigm, which are capable of producing solutions in which both the cut and the maximum subdomain degree are simultaneously minimized. This type of partitionings are critical for existing and emerging applications in VLSI CAD as they allow to both minimize and evenly distribute the interconnects across the physical devices. Our experimental evaluation on the ISPD98 benchmark show that our algorithms produce solutions that when compared against those produced by hMETIS have a maximum subdomain degree that is reduced by up to 36 % while achieving comparable quality in terms of cut. Index Terms — Multi-chip partitioning, placement, interconnect congestion.
On efficiently summarizing categorical databases.
 Frequent itemset mining was initially proposed and has been studied extensively in the context of association rule mining. In recent years, several studies have also extended its application to transaction or document clustering. However, most of the frequent itemset based clustering algorithms need to first mine a large intermediate set of frequent itemsets in order to identify a subset of the most promising ones that can be used for clustering. In this paper, we study how to directly find a subset of high quality frequent itemsets that can be used as a concise summary of the transaction database and to cluster the categorical data. By exploring key properties of the subset of itemsets that we are interested in, we proposed several search space pruning methods and designed an efficient algorithm called SUMMARY. Our empirical results show that SUMMARY runs very fast even when the minimum support is extremely low and scales very well with respect to the database size, and surprisingly, as a pure frequent itemset mining algorithm it is very effective in clustering the categorical data and
On efficiently summarizing categorical databases.
 Frequent itemset mining was initially proposed and has been studied extensively in the context of association rule mining. In recent years, several studies have also extended its application to transaction or document clustering. However, most of the frequent itemset based clustering algorithms need to first mine a large intermediate set of frequent itemsets in order to identify a subset of the most promising ones that can be used for clustering. In this paper, we study how to directly find a subset of high quality frequent itemsets that can be used as a concise summary of the transaction database and to cluster the categorical data. By exploring key properties of the subset of itemsets that we are interested in, we proposed several search space pruning methods and designed an efficient algorithm called SUMMARY. Our empirical results show that SUMMARY runs very fast even when the minimum support is extremely low and scales very well with respect to the database size, and surprisingly, as a pure frequent itemset mining algorithm it is very effective in clustering the categorical data and
BIOKDD06 data mining in Bioinformatics.

Feature%2Dbased recommendation system.
Large information repositories as digital libraries, online shops, etc.
Effective Document Clustering for Large Heterogeneous Law Firm Collections.

HARMONY Efficiently Mining the Best Rules for Classification.
Many studies have shown that rule-based classification algorithms perform well in classifying categorical and sparse high-dimensional databases. However, a fundamental limitation with many rule-based classifiers is that they find the classification rules in a coarsegrained manner. They usually use heuristic methods to prune the search space, and select the rules based on the sequential database covering paradigm. Thus, the so-mined rules may not be the globally best rules for some instances in the training database. To make worse, these algorithms fail to fully exploit some more effective search space pruning methods in order to scale to large databases. In this paper we propose a new classifier, HAR-MONY, which directly mines the final set of classification rules. HARMONY uses an instance-centric rulegeneration approach in the sense that it can assure for each training instance, one of the highest-confidence rules covering this instance is included in the result set, which helps a lot in achieving high classification accuracy. By introducing several novel search strategies and pruning methods into the traditional frequent itemset mining framework, HARMONY also has high efficiency and good scalability. Our thorough performance study with some large text and categorical databases has shown that HARMONY outperforms many well-known classifiers in terms of both accuracy and efficiency, and scales well w.r.t. the database size.
Influence in Ratings%2DBased Recommender Systems An Algorithm%2DIndependent Approach.

Topic%2Ddriven Clustering for Document Datasets.

Mining Chemical Compounds.
Inductive Logic Programming (ILP) is a combination of inductive learning and first-order logic aiming to learn first-order hypotheses from training examples. ILP has a serious bottleneck in an intractably enormous hypothesis search space. This makes existing approaches perform poorly on large-scale real-world datasets. In this research, we propose a technique to make the system handle an enormous search space efficiently by deriving qualitative information into search heuristics. Currently, heuristic functions used in ILP systems are based only on quantitative information, e.g. number of examples covered and length of candidates. We focus on a kind of data consisting of several parts. The approach aims to find hypotheses describing each class by using both individual and relational features of parts. The data can be found in denoting chemical compound structure for Structure-Activity Relationship studies (SAR). We apply the proposed method to extract rules describing chemical activity from their structures. The experiments are conducted on a real-world dataset. The results are compared to existing ILP methods using ten-fold cross validation. 1.
Profile%2Dbased direct kernels for remote homology detection and fold recognition.
Motivation: Remote homology detection between protein sequences is a central problem in computational biology. Supervised learning algorithms based on support vector machines are currently the most effective method for remote homology detection. The performance of these methods depends on how the protein sequences are modeled and on the method used to compute the kernel function between them. Results: We introduce new classes of kernel functions that are constructed by directly combining automatically generated sequence profiles with new and existing approaches for determining the similarity between pairs of protein sequences, which employ effective schemes for scoring the aligned profile positions. Experiments with remote homology detection and fold recognition problems show that these kernels are capable of producing results that are substantially better than those produced by all of the existing state-of-the-art SVM-based methods. In addition, the experiments show that these kernels, even when used in the absence of profiles, produce results that are better than those produced by existing nonprofile-based schemes. 1
Hierarchical Clustering Algorithms for Document Datasets.
Fast and high-quality document clustering algorithms play an important role in providing intuitive navigation and browsing mechanisms by organizing large amounts of information into a small number of meaningful clusters. In particular, hierarchical clustering solutions provide a view of the data at different levels of granularity, making them ideal for people to visualize and interactively explore large document collections.
Finding Frequent Patterns Using Length%2DDecreasing Support Constraints.
Finding prevalent patterns in large amount of data has been one of the major problems in the area of data mining.
Finding Frequent Patterns in a Large Sparse Graph%2A.
This paper presents two algorithms based on the horizontal and vertical pattern discovery paradigms that find the connected subgraphs that have a sufficient number of edgedisjoint embeddings in a single large undirected labeled sparse graph. These algorithms use three different methods to determine the number of the edge-disjoint embeddings of a subgraph that are based on approximate and exact maximum independent set computations and use it to prune infrequent subgraphs. Experimental evaluation on real datasets from various domains show that both algorithms achieve good performance, scale well to sparse input graphs with more than 100,000 vertices and around 200,000 edges, and significantly outperform previously developed algorithms.
Frequent Substructure%2DBased Approaches for Classifying Chemical Compounds.

Gene Classification Using Expression Profiles A Feasibility Study.
As various genome sequencing projects have already been completed or are near completion, genome  researchers are shifting their focus from structural genomics to functional genomics. Functional genomics  represents the next phase, that expands the biological investigation to studying the functionality of genes  of a single organism as well as studying and correlating the functionality of genes across many dierent  organisms. Recently developed methods for monitoring genome-wide mRNA expression changes hold the  promise of allowing us to inexpensively gain insights into the function of unknown genes. In this paper  we focus on evaluating the feasibility of using supervised machine learning methods for determining the  function of genes based solely on their expression proles. We experimentally evaluate the performance  of traditional classication algorithms such as support vector machines and k-nearest neighbors on the  yeast genome, and present new approaches for classication that improve the overall recall with moderate  reductions in precision. Our experiments show that the accuracies achieved for dierent classes varies  dramatically. In analyzing these results we show that the achieved accuracy is highly dependent on  whether or not the genes of that class were signicantly active during the various experimental conditions,  suggesting that gene expression proles can become a viable alternative to sequence similarity searches  provided that the genes are observed under a wide range of experimental conditions.  1 
Prediction of Contact Maps Using Support Vector Machines.
Contact map prediction is of great interest for its application in fold recognition and protein 3D structure determination. In this paper we present a contact-map prediction algorithm that employs Support Vector Machines as the machine learning tool and incorporates various features such as sequence profiles and their conservation, correlated mutation analysis based on various amino acid physicochemical properties, and secondary structure. In addition, we evaluated the effectiveness of the different features on contact map prediction for different fold classes. On average, our predictor achieved a prediction accuracy of 0.2238 with an improvement over a random predictor of a factor 11.7, which is better than reported studies. Our study showed that predicted secondary structure features play an important roles for the proteins containing beta structures. Models based on secondary structure features and CMA features produce different sets of predictions. Our study also suggests that models learned separately for different protein fold families may achieve better performance than a unified model.
Soft clustering criterion functions for partitional document clustering a summary of results.
Recently published studies have shown that partitional clustering algorithms that optimize certain criterion functions, which measure key aspects of inter- and intra-cluster similarity, are very effective in producing hard clustering solutions for document datasets and outperform traditional partitional and agglomerative algorithms. In this paper we study the extent to which these criterion functions can be modified to include soft membership functions and whether or not the resulting soft clustering algorithms can further improve the clustering solutions. Specifically, we focus on four of these hard criterion functions, derive their soft-clustering extensions, and present an experimental evaluation involving twelve different datasets. Our results show that introducing softness into the criterion functions tends to lead to better clustering results for most datasets.
Multi%2Dresource aware partitioning algorithms for FPGAs with heterogeneous resources.
As FPGA densities increase, partitioning-based FPGA placement approaches are becoming increasingly important as they can be used to provide high-quality and computationally scalable solutions. However, modern FPGA architectures incorporate heterogeneous resources, which place additional requirements on the partitioning algorithms because they now need to not only minimize the cut and balance the partitions, but also they must ensure that none of the resources in each partition is oversubscribed. In this paper, we present a number of multilevel multi-resource partitioning algorithms that are guaranteed to produce solutions that balance the utilization of the different resources across the partitions. We evaluate our algorithms on twelve industrial benchmarks ranging in size from 5,236 to 140,118 vertices and show that they achieve minimal degradation in the min-cut while balancing the various resources. Comparing the quality of the solution produced by some of our algorithms against that produced by hME TIS, we show that our algorithms are capable of balancing the different resources while incurring only a 3.3%--5.7% higher cut.
Multi%2Dresource aware partitioning algorithms for FPGAs with heterogeneous resources.
As FPGA densities increase, partitioning-based FPGA placement approaches are becoming increasingly important as they can be used to provide high-quality and computationally scalable solutions. However, modern FPGA architectures incorporate heterogeneous resources, which place additional requirements on the partitioning algorithms because they now need to not only minimize the cut and balance the partitions, but also they must ensure that none of the resources in each partition is oversubscribed. In this paper, we present a number of multilevel multi-resource partitioning algorithms that are guaranteed to produce solutions that balance the utilization of the different resources across the partitions. We evaluate our algorithms on twelve industrial benchmarks ranging in size from 5,236 to 140,118 vertices and show that they achieve minimal degradation in the min-cut while balancing the various resources. Comparing the quality of the solution produced by some of our algorithms against that produced by hME TIS, we show that our algorithms are capable of balancing the different resources while incurring only a 3.3%--5.7% higher cut.

SUMMARY Efficiently Summarizing Transactions for Clustering.
Frequent itemset mining was initially proposed and has been studied extensively in the context of association rule mining. In recent years, several studies have also extended its application to the transaction (or document) classification and clustering. However, most of the frequent-itemset based clustering algorithms need to first mine a large intermediate set of frequent itemsets in order to identify a subset of the most promising ones that can be used for clustering. In this paper, we study how to directly find a subset of high quality frequent itemsets that can be used as a concise summary of the transaction database and to cluster the categorical data. By exploring some properties of the subset of itemsets that we are interested in, we proposed several search space pruning methods and designed an e#cient algorithm called SUMMARY. Our empirical results have shown that SUMMARY runs very fast even when the minimum support is extremely low and scales very well with respect to the database size, and surprisingly, as a pure frequent itemset mining algorithm it is very e#ective in clustering the categorical data and summarizing the dense transaction databases.
GREW%2DA Scalable Frequent Subgraph Discovery Algorithm.
Existing algorithms that mine graph datasets to discover patterns corresponding to frequently occurring subgraphs can operate efficiently on graphs that are sparse, contain a large number of relatively small connected components, have vertices with low and bounded degrees, and contain well-labeled vertices and edges. However, there are a number of applications that lead to graphs that do not share these characteristics, for which these algorithms highly become unscalable. In this paper we propose a heuristic algorithm called GREW to overcome the limitations of existing complete or heuristic frequent subgraph discovery algorithms. GREW is designed to operate on a large graph and to find patterns corresponding to connected subgraphs that have a large number of vertex-disjoint embeddings. Our experimental evaluation shows that GREW is efficient, can scale to very large graphs, and find non-trivial patterns that cover large portions of the input graph and the lattice of frequent patterns.

BAMBOO Accelerating Closed Itemset Mining by Deeply Pushing the Length%2DDecreasing Support Constraint.
Previous study has shown that mining frequent patterns with length-decreasing support constraint is very helpful in removing some uninteresting patterns based on the observation that short patterns will tend to be interesting if they have a high support, whereas long patterns can still be very interesting even if their support is relatively low. However, a large number of non-closed (i.e., redundant) patterns can still not be filtered out by simply applying the lengthdecreasing support constraint. As a result, a more desirable pattern discovery task could be mining closed patterns under the length-decreasing support constraint. In this paper, we study...
Finding Frequent Patterns in a Large Sparse Graph.
This paper presents two algorithms based on the horizontal and vertical pattern discovery paradigms that find the connected subgraphs that have a sufficient number of edgedisjoint embeddings in a single large undirected labeled sparse graph. These algorithms use three different methods to determine the number of the edge-disjoint embeddings of a subgraph that are based on approximate and exact maximum independent set computations and use it to prune infrequent subgraphs. Experimental evaluation on real datasets from various domains show that both algorithms achieve good performance, scale well to sparse input graphs with more than 100,000 vertices and around 200,000 edges, and significantly outperform previously developed algorithms.
Item%2Dbased top%2DN recommendation algorithms.
this paper we present one such class of model-based recommendation algorithms that first determines the similarities between the various items and then uses them to identify the set of items to be recommended. The key steps in this class of algorithms are (i) the method used to compute the similarity between the items, and (ii) the method used to combine these similarities in order to compute the similarity between a basket of items and a candidate recommender item. Our experimental evaluation on eight real datasets shows that these item-based algorithms are up to two orders of magnitude faster than the traditional user-neighborhood based recommender systems and provide recommendations with comparable or better quality
Selective Markov models for predicting Web page accesses.
The problem of predicting a user&#039;s behavior on a web-site has gained importance due to the rapid  growth of the world-wide-web and the need to personalize and influence a user&#039;s browsing experience.  Markov models and their variations have been found well suited for addressing this problem. Of the  different variations or Markov models it is generally found that higher-order Markov models display high  predictive accuracies. However higher order models are also extremely complicated due to their large  number of states that increases their space and runtime requirements. In this paper we present different  techniques for intelligently selecting parts of different order Markov models so that the resulting model  has a reduced state complexity and improved prediction accuracy. We have tested our models on various  datasets and have found that their performance is consistently superior to that obtained by higher-order  Markov models.  Keywords: world wide web, web mining, Markov models, p...
An Efficient Algorithm for Discovering Frequent Subgraphs.
Abstract — Over the years, frequent itemset discovery algorithms have been used to find interesting patterns in various application areas. However, as data mining techniques are being increasingly applied to non-traditional domains, existing frequent pattern discovery approach cannot be used. This is because the transaction framework that is assumed by these algorithms cannot be used to effectively model the datasets in these domains. An alternate way of modeling the objects in these datasets is to represent them using graphs. Within that model, one way of formulating the frequent pattern discovery problem is as that of discovering subgraphs that occur frequently over the entire set of graphs. In this paper we present a computationally efficient algorithm, called FSG, for finding all frequent subgraphs in large graph datasets. We experimentally evaluate the performance of FSG using a variety of real and synthetic datasets. Our results show that despite the underlying complexity associated with frequent subgraph discovery, FSG is effective in finding all frequently occurring subgraphs in datasets containing over 200,000 graph transactions and scales linearly with respect to the size of the dataset. Index Terms — Data mining, scientific datasets, frequent pattern discovery, chemical compound datasets.
Empirical and Theoretical Comparisons of Selected Criterion Functions for Document Clustering.

Parallel tree%2Dprojection%2Dbased sequence mining algorithms.

Prediction of Contact Maps Using Support Vector Machines.
Contact map prediction is of great interest for its application in fold recognition and protein 3D structure determination. In this paper we present a contact-map prediction algorithm that employs Support Vector Machines as the machine learning tool and incorporates various features such as sequence profiles and their conservation, correlated mutation analysis based on various amino acid physicochemical properties, and secondary structure. In addition, we evaluated the effectiveness of the different features on contact map prediction for different fold classes. On average, our predictor achieved a prediction accuracy of 0.2238 with an improvement over a random predictor of a factor 11.7, which is better than reported studies. Our study showed that predicted secondary structure features play an important roles for the proteins containing beta structures. Models based on secondary structure features and CMA features produce different sets of predictions. Our study also suggests that models learned separately for different protein fold families may achieve better performance than a unified model.
Intelligent metasearch engine for knowledge management.

Multi.Objective Hypergraph Partitioning Algorithms for Cut and Maximum Subdomain Degree Minimization.
Abstract — In this paper we present a family of multi-objective hypergraph partitioning algorithms based on the multilevel paradigm, which are capable of producing solutions in which both the cut and the maximum subdomain degree are simultaneously minimized. This type of partitionings are critical for existing and emerging applications in VLSI CAD as they allow to both minimize and evenly distribute the interconnects across the physical devices. Our experimental evaluation on the ISPD98 benchmark show that our algorithms produce solutions that when compared against those produced by hMETIS have a maximum subdomain degree that is reduced by up to 36 % while achieving comparable quality in terms of cut. Index Terms — Multi-chip partitioning, placement, interconnect congestion.
Frequent Sub%2DStructure%2DBased Approaches for Classifying Chemical Compounds.
In this paper we study the problem of classifying chemical compound datasets. We present a sub-structure-based  classification algorithm that decouples the sub-structure discovery process from the classification model construction  and uses frequent subgraph discovery algorithms to find all topological and geometric sub-structures present in the  dataset. The advantage of our approach is that during classification model construction, all relevant sub-structures  are available allowing the classifier to intelligently select the most discriminating ones. The computational scalability  is ensured by the use of highly efficient frequent subgraph discovery algorithms coupled with aggressive feature  selection. Our experimental evaluation on eight different classification problems shows that our approach is computationally  scalable and outperforms existing schemes by 10% to 35%, on the average.
Multi%2DConstraint Mesh Partitioning for Contact%2FImpact Computations.
We present a novel approach for decomposing contact/impact computations in which the mesh elements come in contact with each other during the course of the simulation. Effective decomposition of these computations poses a number of challenges as it needs to both balance the computations and minimize the amount of communication that is performed during the finite element and the contact search phase. Our approach achieves the first goal by partitioning the underlying mesh such that it simultaneously balances both the work that is performed during the finite element phase and that performed during contact search phase, while producing subdomains whose boundaries consist of piecewise axes-parallel lines or planes. The second goal is achieved by using a decision tree to decompose the space into rectangular or box-shaped regions that contain contact points from a single partition. Our experimental evaluation on a sequence of 100 meshes, shows that this new approach can significantly reduce the communication overhead over existing algorithms. 1
Perimeter%2Ddegree a priori metric for directly measuring and homogenizing interconnection complexity in multilevel placement.
In this paper, we describe an accurate metric (perimeter-degree) for measuring interconnection complexity and effective use of it for controlling congestion in a multilevel framework. Perimeter-degree is useful for uniformly spreading interconnection density. In modern designs interconnects consume significant area and power. By making interconnect spread homogeneous, it is possible to improve routability as well as power dissipation distribution.
Predicting the Performance of Randomized Parallel Search An Application to Robot Motion Planning.

Automated Approaches for Classifying Structures.
In this paper we study the problem of classifying chemical compound datasets. We present an algorithm that first  mines the chemical compound dataset to discover discriminating sub-structures; these discriminating sub-structures  are used as features to build a powerful classifier. The advantage of our classification technique is that it requires  very little domain knowledge and can easily handle large chemical datasets. We evaluated the performance of our  classifier on two widely available chemical compound datasets and have found it to give good results.

Using conjunction of attribute values for classification.
Advances in the efficient discovery of frequent itemsets in large databases have led to the development of a number of schemes that use frequent itemsets to aid in the development of accurate and efficient classifiers. These approaches use the frequent itemsets to generate a set of composite features that expand the dimensionality of the underlying dataset. In this paper, we build upon this work and (i) present a variety of schemes for composite feature selection that achieve a substantial reduction in the number of features without adversely affecting the accuracy gains, and (ii) show (both analytically and experimentally) that the composite feature space can lead to improved classification models in the context of support vector machines, in which the dimensionality can automatically be expanded by the use of appropriate kernel functions.
Evaluation of hierarchical clustering algorithms for document datasets.
Fast and high-quality document clustering algorithms play an important role in providing intuitive navigation and browsing mechanisms by organizing large amounts of information into a small number of meaningful clusters. In particular, hierarchical clustering solutions provide a view of the data at different levels of granularity, making them ideal for people to visualize and interactively explore large document collections.

Discovering Frequent Geometric Subgraphs.
As data mining techniques are being increasingly applied to non-traditional domains, existing approaches  for finding frequent itemsets cannot be used as they cannot model the requirement of these  domains. An alternate way of modeling the objects in these data sets, is to use a graph to model the  database objects. Within that model, the problem of finding frequent patterns becomes that of discovering  subgraphs that occur frequently over the entire set of graphs. In this paper we present a computationally  e#cient algorithm for finding frequent geometric subgraphs in a large collection of geometric graphs. Our  algorithm is able to discover geometric subgraphs that can be rotation, scaling and translation invariant,  and it can accommodate inherent errors on the coordinates of the vertices. We evaluated the performance  of the algorithm using a large database of over 20,000 real two dimensional chemical structures,  and our experimental results show that our algorithms requires relatively little time, can accommodate  low support values, and scales linearly on the number of transactions.
SLPMiner An Algorithm for Finding Frequent Sequential Patterns Using Length%2DDecreasing Support Constraint.
Over the years, a variety of algorithms for finding frequent sequential patterns in very large sequential databases have been developed. The key feature in most of these algorithms is that they use a constant support constraint to control the inherently exponential complexity of the problem. In general, patterns that contain only a few items will tend to be interesting if they have a high support, whereas long patterns can still be interesting even if their support is relatively small. Ideally, we desire to have an algorithm that finds all the frequent patterns whose support decreases as a function of their length. In this paper we present an algorithm called SLPMiner, that finds all sequential patterns that satisfy a length-decreasing support constraint. SLPMiner combines an efficient database-projection-based approach for sequential pattern discovery with three effective database pruning methods that dramatically reduce the search space. Our experimental evaluation shows that SLPMiner, by effectively exploiting the length-decreasing support constraint, is up to two orders of magnitude faster, and its runtime increases gradually as the average length of the sequences (and the discovered frequent patterns) increases.
Improve Precategorized Collection Retrieval by Using Supervised Term Weighting Schemes.
The emergence of the world-wide-web has led to an increased interest in methods for searching for information. A key characteristic of many of the online document collections is that the documents have predefined category information, for example, the variety of scientific articles accessible via digital libraries (e.g., ACM, IEEE, etc.), medical articles, news-wires, and various directories (e.g., Yahoo, OpenDirectory Project, etc.). However, most previous information retrieval systems have not taken the pre-existing category information into account. In this paper, we proposed weight adjustment schemes based upon the category information in the vector-space model, which are able to select the most content specific and discriminating features. Our experimental results on TREC data sets show that the pre-existing category information does provide additional beneficial information to improve retrieval. The proposed weight adjustment schemes perform better than the vector-space model with the inverse document frequency (IDF) weighting scheme when queries are less specific. The proposed weighting schemes can also benefit retrieval when clusters are used as an approximation to categories.
Evaluation of Techniques for Classifying Biological Sequences.
In recent years we have witnessed an exponential increase in the amount of biological information, either DNA  or protein sequences, that has become available in public databases. This has been followed by an increased interest  in developing computational techniques to automatically classify these large volumes of sequence data into various  categories corresponding to either their role in the chromosomes, their structure, and/or their function. In this paper we  evaluate some of the widely-used sequence classification algorithms and develop a framework for modeling sequences  in a fashion so that traditional machine learning algorithms, such as support vector machines, can be applied easily.
Expert agreement and content based reranking in a meta search environment using Mearf.

Parallel static and dynamic multi%2Dconstraint graph partitioning.

Gene Classification using Expression Profiles A Feasibility Study.
As various genome sequencing projects have already been completed or are near completion, genome  researchers are shifting their focus from structural genomics to functional genomics. Functional genomics  represents the next phase, that expands the biological investigation to studying the functionality of genes  of a single organism as well as studying and correlating the functionality of genes across many dierent  organisms. Recently developed methods for monitoring genome-wide mRNA expression changes hold the  promise of allowing us to inexpensively gain insights into the function of unknown genes. In this paper  we focus on evaluating the feasibility of using supervised machine learning methods for determining the  function of genes based solely on their expression proles. We experimentally evaluate the performance  of traditional classication algorithms such as support vector machines and k-nearest neighbors on the  yeast genome, and present new approaches for classication that improve the overall recall with moderate  reductions in precision. Our experiments show that the accuracies achieved for dierent classes varies  dramatically. In analyzing these results we show that the achieved accuracy is highly dependent on  whether or not the genes of that class were signicantly active during the various experimental conditions,  suggesting that gene expression proles can become a viable alternative to sequence similarity searches  provided that the genes are observed under a wide range of experimental conditions.  1 
A scalable algorithm for clustering protein sequences.
×�Ñ�Ð�Ö�ØÝ ÀÓÛ�Ú�Ö ÑÓ×Ø Ó � Ø��× � Ñ�Ø�Ó� × Ø�Ò � ØÓ ��Ú � � ÓÑÔÙØ�Ø�ÓÒ�Ð ÓÑÔÐ�Ü�ØÝ Ø��Ø � × �Ø Ð��×Ø ÕÙ��Ö�Ø � ÓÒ Ø�� ÒÙÑ��Ö Ó � ×�ÕÙ�Ò � × ÁÒ Ø�� × Ô�Ô�Ö Û � ÔÖ�×�ÒØ�Ò�ÒØ�Ö�ÐÝ ��«�Ö�ÒØ �ÔÔÖÓ �  � ØÓ ÔÖÓØ��Ò ÐÙ×Ø�Ö�Ò � Ø��Ø �Ó� × ÒÓØ Ö�ÕÙ�Ö� �Ò �ÐÐ ����Ò×Ø �ÐÐ �Ò�ÐÝ×� × �Ò � Ù×� ×  � Ò��Ö Ð�Ò��Ö ÓÑÔÐ�Ü

Evaluation of Item%2DBased Top%2DN Recommendation Algorithms.
The explosive growth of the world-wide-web and the emergence of e-commerce has led to the development of  recommender systems---a personalized information filtering technology used to identify a set of N items that will  be of interest to a certain user. User-based Collaborative filtering is the most successful technology for building  recommender systems to date, and is extensively used in many commercial recommender systems. Unfortunately, the  computational complexity of these methods grows linearly with the number of customers that in typical commercial  applications can grow to be several millions. To address these scalability concerns item-based recommendation  techniques have been developed that analyze the user-item matrix to identify relations between the different items,  and use these relations to compute the list of recommendations.  In this paper we present one such class of item-based recommendation algorithms that first determine the similarities  between the various ite...
Graph Partitioning for Dynamic%2C Adaptive and Multi%2Dphase Scientific Simulations.
The efficient execution of scientific simulations on HPC systems requires a partitioning of the underlying mesh among the processors such that the load is balanced and the inter-processor communication is minimized. Graph partitioning algorithms have been applied with much success for this purpose. However, the parallelization of multi-phase and multi-physics computations poses new challenges that require fundamental advances in graph partitioning technology. In addition, most existing graph partitioning algorithms are not suited for the newer heterogeneous highperformance computing platforms. This talk will describe research efforts in our group that are focused on developing novel multi-constraint and multi-objective graph partitioning algorithms that can support the advancing state-ofthe-art in numerical simulation technologies. In addition, we will present our preliminary work on new partitioning algorithms that are well suited for heterogeneous architectures. 1.


A Scalable Algorithm for Clustering Sequential Data.
Many scientific and commercial domains have seen an enormous growth of data in recentyears. Such  data sets have inherent sequential nature. The clustering of such data is useful for various purposes.  Over the years, many methods havebeendeveloped for clustering objects according to their similarity.  However, in contexts of sequential data these methods tend to have a computational complexity that is  at least quadratic on the number of sequences, as they require an all-against-all initial analysis. In this  paper we presentanentirely different approach to sequence clustering that does not require an all-againstall  analysis and uses a near-linear complexity K-means based clustering algorithm. Our experimental  evaluation in different domains show that this approach is not only scalable, but also leads to reasonably  good clusters.   
Frequent Subgraph Discovery.
Over the years, frequent itemset discovery algorithms have been used to solve various interesting problems. As data mining techniques are being increasingly applied to non-traditional domains, existing approaches for finding frequent itemsets cannot be used as they cannot model the requirement of these domains. An alternate way of modeling the objects in these data sets, is to use a graph to model the database objects. Within that model, the problem of finding frequent patterns becomes that of discovering subgraphs that occur frequently over the entire set of graphs. In this paper we present a computationally efficient algorithm for finding all frequent subgraphs in large graph databases. We evaluated the performance of the algorithm by experiments with synthetic datasets as well as a chemical compound dataset. The empirical results show that our algorithm scales linearly with the number of input transactions and it is able to discover frequent subgraphs from a set of graph transactions reasonably fast, even though we have to deal with computationally hard problems such as canonical labeling of graphs and subgraph isomorphism which are not necessary for traditional frequent itemset discovery.

Text Categorization Using Weight Adjusted k%2DNearest Neighbor Classification.
Categorization of documents is challenging, as the number of discriminating words can be very large. We present a nearest neighbor classification scheme for text categorization in which the importance of discriminating words is learned using mutual information and weight adjustment techniques. The nearest neighbors for a particular document are then computed based on the matching words and their weights. We evaluate our scheme on both synthetic and real world documents. Our experiments with synthetic data sets show that this scheme is robust under different emulated conditions. Empirical results on real world documents demonstrate that this scheme outperforms state of the art classification algorithms such as C4.5, RIPPER, Rainbow, and PEBLS.
Multilevel algorithms for generating coarse grids for multigrid methods.
Geometric Multigrid methods have gained widespread acceptance for solving large systems of linear equations, especially for structured grids. One of the
Item%2Dbased collaborative filtering recommendation algorithms.

When being Weak is Brave Privacy in Recommender Systems

Privacy Risks in Recommender Systems.
this article, we can state some general guidelines. Like most problems in computer security, the ideal deterrents are better awareness of the issues and more openness in how systems operate in the marketplace. In particular, individual sites should clearly state the policies and methodologies they employ with recommender systems, including the role played by straddlers in their data sets and system designs. This is especially true for sites with multiple homogeneous networks (as in Figures 6c and 6d).   By conveying benefits and risks to users intuitively, recommender systems could achieve greater acceptance. We envisage three general ways to highlight the implications of our analyses. # Present plots of benefit and risk versus usermodifiable parameters such as ratings, w, and l (if the algorithm allows their direct specification) to allow users to make informed choices about their levels of involvement
Wavefront Diffusion and LMSR Algorithms for Dynamic Repartitioning of Adaptive Meshes.
Existing state-of-the-art schemes for dynamic repartitioning of adaptive meshes can be classified as either diffusion-based schemes or scratch-remap schemes. We present a new scratch-remap scheme called Locally-Matched Multilevel Scratch-Remap (or simply LMSR). The LMSR scheme tries to compute a partitioning that has a high overlap with the existing partitioning. We show that LMSR decreases the amount of vertex migration required to balance the graph compared to current scratch-remap schemes, particularly for slightly imbalanced graphs. We describe a new diffusion-based scheme that we refer to as Wavefront Diffusion. In Wavefront Diffusion, the flow of vertices moves in a wavefront from overweight to underweight domains. We show that Wavefront Diffusion obtains significantly lower vertex migration requirements while maintaining similar or better edge-cut results compared to existing diffusion algorithms, especially for highly imbalanced graphs. Furthermore, we compare Wavefront Diffusi...
Analysis of recommendation algorithms for e%2Dcommerce.
Recommender systems apply statistical and knowledge discovery techniques to the problem of making product recommendations during a live customer interaction and they are achieving widespread success in E-Commerce nowadays. In this paper, we investigate several techniques for analyzing large-scale purchase and preference data for the purpose of producing useful recommendations to customers. In particular, we apply a collection of algorithms such as traditional data mining, nearest-neighbor collaborative ltering, and dimensionality reduction on two dierent data sets. The rst data set was derived from the web-purchasing transaction of a large E-commerce company whereas the second data set was collected from MovieLens movie recommendation site. For the experimental purpose, we divide the recommendation generation process into three sub processes{ representation of input data, neighborhood formation, and recommendation generation. We devise dierenttechniques for dierent sub processes a...
Fast Supervised Dimensionality Reduction Algorithm with Applications to Document Categorization %26 Retrieval.
Retrieval techniques based on dimensionality reduction, such as Latent Semantic Indexing (LSI), have been shown to improve the quality of the information being retrieved by capturing the latent meaning of the words present in the documents. Unfortunately, the high computational and memory requirements of LSI and its inability to compute an effective dimensionality reduction in a supervised setting limits its applicability. In this paper we present a fast supervised dimensionality reduction algorithm that is derived from the recently developed cluster-based unsupervised dimensionality reduction algorithms. We experimentally evaluate the quality of the lower dimensional spaces both in the context of document categorization and improvements in retrieval performance on a variety of different document collections. Our experiments show that the lower dimensional spaces computed by our algorithm consistently improve the performance of traditional algorithms such as C4.5, k-nearest- neighbor, ...
Memory Management Techniques for Gang Scheduling.

Parallel Multilevel Algorithms for Multi%2Dconstraint Graph Partitioning %28Distinguished Paper%29.

Load Balancing Across Near%2DHomogeneous Multi%2DResource Servers.
An emerging model for computational grids interconnects similar multi-resource servers from distributed sites. A job submitted to the grid can be executed by any of the servers; however, resource size or balance may be different across servers. One approach to resource management for this grid is to layer a global load distribution system on top of the local job management systems at each site. Unfortunately, classical load distribution policies fail on two aspects when applied to a multi-resource server grid. First, simple load indices may not recognize that a resource imbalance exists at a server. Second, classical job selection policies do not actively correct such a resource imbalanced state. We show through simulation that new policies based on resource balancing perform consistently better than the classical load distribution strategies. 1.
Graph Partitioning for Dynamic%2C Adaptive%2C and Multi%2Dphase Computations.

Centroid%2DBased Document Classification Analysis and Experimental Results.
. In this paper we present a simple linear-time centroid-based document  classification algorithm, that despite its simplicity and robust performance,  has not been extensively studied and analyzed. Our experiments show that this  centroid-based classifier consistently and substantially outperforms other algorithms  such as Naive Bayesian, k-nearest-neighbors, and C4.5, on a wide range  of datasets. Our analysis shows that the similarity measure used by the centroidbased  scheme allows it to classify a new document based on how closely its behavior  matches the behavior of the documents belonging to different classes. This  matching allows it to dynamically adjust for classes with different densities and  accounts for dependencies between the terms in the different classes.  1 Introduction  We have seen a tremendous growth in the volume of online text documents available on the Internet, digital libraries, news sources, and company-wide intranets. It has been forecasted that these docu...
A Unified Algorithm for Load%2Dbalancing Adaptive Scientific Simulations.

Scalable Parallel Data Mining for Association Rules.
One of the important problems in data mining is discovering association rules from databases of transactions where each transaction consists of a set of items. The most time consuming operation in this discovery process is the computation of the frequency of the occurrences of interesting subset of items (called candidates) in the database of transactions. To prune the exponentially large space of candidates, most existing algorithms, consider only those candidates that have a user defined minimum support. Even with the pruning, the task of finding all association rules requires a lot of computation power and time. Parallel computers offer a potential solution to the computation requirement of this task, provided efficient and scalable parallel algorithms can be designed. In this paper, we present two new parallel algorithms for mining association rules. The Intelligent Data Distribution algorithm efficiently uses aggregate memory of the parallel computer by employing intelligent candi...
Graph partitioning and parallel computing.
Abstract. Recently, a number of researchers have investigated a class of graph partitioning algorithms that reduce the size of the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partition for the original graph [Bui and Jones, Proc.
Multilevel k%2Dway Hypergraph Partitioning.
In this paper, we present a new multilevel k-way hypergraph partitioning algorithm that substantially outperforms the existing state-of-the-art K-PM/LR algorithm for multi-way partitioning. both for optimizing local as well as global objectives. Experiments on the ISPD98 benchmark suite show that the partitionings produced by our scheme are on the average 15% to 23% better than those produced by the K-PM/LR algorithm, both in terms of the hyperedge cut as well as the (K  -  1) metric. Furthermore, our algorithm is significantly faster, requiring 4 to 5 times less time than that required by K-PM/LR. 1 Introduction  Hypergraph partitioning is an important problem with extensive application to many areas, including VLSI design [10], efficient storage of large databases on disks [14], and data mining [13]. The problem is to partition the vertices of a hypergraph into k roughly equal parts, such that a certain objective function defined over the hyperedges is optimized. A commonly used obje...
A New Algorithm for Multi%2Dobjective Graph Partitioning.
. Recently, a number of graph partitioning applications have emerged with additional requirements that the traditional graph partitioning model alone cannot effectively handle. One such class of problems is those in which multiple objectives, each of which can be modeled as a sum of weights of the edges of a graph, must be simultaneously optimized. This class of problems can be solved utilizing a multi-objective graph partitioning algorithm. We present a new formulation of the multi-objective graph partitioning problem and describe an algorithm that computes partitionings with respect to this formulation. We explain how this algorithm provides the user with a fine-tuned control of the tradeoffs among the objectives, results in predictable partitionings, and is able to handle both similar and dissimilar objectives. We show that this algorithm is better able to find a good tradeoff among the objectives than partitioning with respect to a single objective only. Finally, we show that by mo...
Multi%2DCapacity Bin Packing Algorithms with Applications to Job Scheduling under Multiple Constraints.

Efficient Parallel Algorithms for Mining Associations.

Dynamic Repartitioning of Adaptively Refined Meshes.

PSPASES An Efficient and Scalable Parallel Sparse Direct Solver.
Many problems in engineering and scientific domains require solving large sparse systems of linear equations, as a computationally intensivesteptowards the final solution. It has long beenachallenge to develop efficient parallel formulations of sparse direct solvers due to several different complex steps involved in the process. In this paper, we describe PSPASES, one of the first efficient, portable, and robust scalable parallel solvers for sparse symmetric positive definite linear systems that wehavedeveloped. We discuss the algorithmic and implementation issues involved in its development# and present performance and scalability results on CrayT3E and SGI Origin 2000. PSPASES could solve the largest sparse system (1 million equations) ever solved by a direct method, with the highest performance (51 GFLOPS for Cholesky factorization) ever reported. 
Document Categorization and Query Generation on the World Wide Web Using WebACE.
We present WebACE, an agent for exploring and categorizing documents on the World Wide Web based on a user profile. The heart of the agent is an unsupervised categorization of a set of documents, combined with a process for generating new queries that is used to search for new related documents and for filtering the resulting documents to extract the ones most closely related to the starting set. The document categories are not given a priori. We present the overall architecture and describe two novel algorithms which provide significant improvement over traditional clustering algorithms and form the basis for the query generation and search component of the agent. We report on the results of our experiments comparing these new algorithms with more traditional clustering algorithms and we show that our algorithms are fast and scalable.
Chameleon Hierarchical Clustering Using Dynamic Modeling.
Many advanced algorithms have difficulty dealing with highly variable clusters that do not follow a preconceived model. By basing its selections on both interconnectivity and closeness, the Chameleon algorithm yields accurate results for these highly variable clusters.
Multilevel hypergraph partitioning applications in VLSI domain.
In this paper, we present a new hypergraphpartitioning algorithm that is based on the multilevel paradigm. In the multilevel paradigm, a sequence of successively coarser hypergraphs is constructed. A bisection of the smallest hypergraph is computed and it is used to obtain a bisection of the original hypergraph by successively projecting and refining the bisection to the next level finer hypergraph. We have developed new hypergraph coarsening strategies within the multilevel framework. We evaluate their performance both in terms of the size of the hyperedge cut on the bisection, as well as on the run time for a number of very large scale integration circuits. Our experiments show that our multilevel hypergraph-partitioning algorithm produces high-quality partitioning in a relatively small amount of time. The quality of the partitionings produced by our scheme are on the average 6%–23 % better than those produced by other state-of-the-art schemes. Furthermore, our partitioning algorithm is significantly faster, often requiring 4–10 times less time than that required by the other schemes. Our multilevel hypergraph-partitioning algorithm scales very well for large hypergraphs. Hypergraphs with over 100 000 vertices can be bisected in a few minutes on today’s workstations. Also, on the large hypergraphs, our scheme outperforms other schemes (in hyperedge cut) quite consistently with larger margins (9%–30%).  
WebACE A Web Agent for Document Categorization and Exploration.
We propose an agent for exploring and categorizing documents on the World Wide Web. The heart of the agent is an automatic categorization of a set of documents, combined with a process for generating new queries used to search for new related documents and filtering the resulting documents to extract the set of documents most closely related to the starting set. The document categories are not given a-priori. We present the overall architecture and describe two novel algorithms which provide significant improvement over traditional clustering algorithms and form the basis for the query generation and search component of the agent.  1 Introduction  The World Wide Web is a vast resource of information and services that continues to grow rapidly. Powerful search engines have been developed to aid in locating unfamiliar documents by category, contents, or subject. Relying on large indexes to documents located on the Web, search engines determine the URLs of those documents satisfying a use...
ScalParC A New Scalable and Efficient Parallel Classification Algorithm for Mining Large Datasets.
In this paper, we present ScalParC (Scalable Parallel Classifier), a new parallel formulation of a decision tree based classification process. Like other state-of-the-art decision tree classifiers such as SPRINT, ScalParC is suited for handling large datasets. We show that existing parallel formulation of SPRINT is unscalable, whereas ScalParC is shown to be scalable in both runtime and memory requirements. We present the experimental results of classifying up to 6.4 million records on up to 128 processors of Cray T3D, in order to demonstrate the scalable behavior of ScalParC. A key component of ScalParC is the parallel hash table. The proposed parallel hashing paradigm can be used to parallelize other algorithms that require many concurrent updates to a large hash table.  1 Introduction  Classification is an important problem in the rapidly emerging field of data mining. The problem can be stated as follows. We are given a training dataset consisting of records. Each record is identif...
Load Balancing of Dynamic and Adaptive Mesh%2DBased Computations.

Hypergraph Based Clustering in High%2DDimensional Data Sets A Summary of Results.
Clustering of data in a large dimension space is of a great interest in many data mining applications. In this paper, we propose a method for clustering of data in a high dimensional space based on a hypergraph model. In this method, the relationship present in the original data in high dimensional space are mapped into a hypergraph. A hyperedge represents a relationship (affinity) among subsets of data and the weight of the hyperedge reflects the strength of this affinity. A hypergraph partitioning algorithm is used to find a partitioning of the vertices such that the corresponding data items in each partition are highly related and the weight of the hyperedges cut by the partitioning is minimized. We present results of experiments on two different data sets: S&amp;P500 stock data for the period of 1994-1996 and protein coding data. These experiments demonstrate that our approach is applicable and effective in high dimensional datasets. 1 Introduction  Clustering in data mining is a disco...
A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering.

Multilevel k%2Dway Partitioning Scheme for Irregular Graphs.

Multilevel Hypergraph Partitioning Application in VLSI Domain.
In this paper, we present a new hypergraphpartitioning algorithm that is based on the multilevel paradigm. In the multilevel paradigm, a sequence of successively coarser hypergraphs is constructed. A bisection of the smallest hypergraph is computed and it is used to obtain a bisection of the original hypergraph by successively projecting and refining the bisection to the next level finer hypergraph. We have developed new hypergraph coarsening strategies within the multilevel framework. We evaluate their performance both in terms of the size of the hyperedge cut on the bisection, as well as on the run time for a number of very large scale integration circuits. Our experiments show that our multilevel hypergraph-partitioning algorithm produces high-quality partitioning in a relatively small amount of time. The quality of the partitionings produced by our scheme are on the average 6%–23 % better than those produced by other state-of-the-art schemes. Furthermore, our partitioning algorithm is significantly faster, often requiring 4–10 times less time than that required by the other schemes. Our multilevel hypergraph-partitioning algorithm scales very well for large hypergraphs. Hypergraphs with over 100 000 vertices can be bisected in a few minutes on today’s workstations. Also, on the large hypergraphs, our scheme outperforms other schemes (in hyperedge cut) quite consistently with larger margins (9%–30%).  
Clustering Based On Association Rule Hypergraphs.
Clustering in data mining is a discovery process that groups a set of data such that the intracluster similarity is maximized and the intercluster similarity is minimized. These discovered clusters are used to explain the characteristics of the data distribution. In this paper we propose a new methodology for clustering related items using association rules, and clustering related transactions using clusters of items. Our approach is linearly scalable with respect to the number of transactions. The frequent item-sets used to derive association rules are also used to group items into a hypergraph edge, and a hypergraph partitioning algorithm is used to find the clusters. Our experiments indicate that clustering using association rule hypergraphs holds great promise in several application domains. Our experiments with stock-market data and congressional voting data show that this clustering scheme is able to successfully group items that belong to the same group. Clustering of items can ...
Repartitioning of Adaptive Meshes Experiments with Multilevel Diffusion.

A Coarse%2DGrain Parallel Formulation of Multilevel k%2Dway Graph Partitioning Algorithm.
In this paper we present a parallel formulation of a multilevel k-way graph partitioning algorithm, that is particularly suited for message-passing libraries that have high latency. The multilevel k-way partitioning algorithm reduces the size of the graph by successively collapsing vertices and edges (coarsening phase), finds a k-way partitioning of the smaller graph, and then it constructs a k-way partitioning for the original graph by projecting and refining the partition to successively finer graphs (uncoarsening phase). Our algorithm is able to achieve a high degree of concurrency, while maintaining the high quality partitions produced by the serial algorithm.  
Design and Implementation of a Scalable Parallel Direct Solver for Sparse Symmetric Positive Definite Systems Preliminary Results.
Solving large sparse systems of linear equations is at the core of many problems in engineering and scientific computing. It has long been a challenge to develop parallel formulations of sparse direct solvers due to several different complex steps involved in the process. In this paper, we describe one of the first efficient, practical, and robust parallel solvers for sparse symmetric positive definite linear systems that we have developed and discuss the algorithmic and implementation issues involved in its development. 1 Introduction  Solving large sparse systems of linear equations is at the heart of many engineering and scientific computing applications. There are two methods to solve these systems - direct and iterative. Direct methods are preferred for many applications because of various properties of the method and the nature of the application. A wide class of sparse linear systems arising in practice have a symmetric positive definite (SPD) coefficient matrix. The problem is ...
Role of Message%2DPassing in Performance Oriented Parallel Programming.

Scalable Parallel Data Mining for Association Rules.
One of the important problems in data mining is discovering association rules from databases of transactions where each transaction consists of a set of items. The most time consuming operation in this discovery process is the computation of the frequency of the occurrences of interesting subset of items (called candidates) in the database of transactions. To prune the exponentially large space of candidates, most existing algorithms, consider only those candidates that have a user defined minimum support. Even with the pruning, the task of finding all association rules requires a lot of computation power and time. Parallel computers offer a potential solution to the computation requirement of this task, provided efficient and scalable parallel algorithms can be designed. In this paper, we present two new parallel algorithms for mining association rules. The Intelligent Data Distribution algorithm efficiently uses aggregate memory of the parallel computer by employing intelligent candi...
Highly Scalable Parallel Algorithms for Sparse Matrix Factorization.
In this paper, we describe a scalable parallel algorithm for sparse matrix factorization, analyze their performance and scalability, and present experimental results for up to 1024 processors on a Cray T3D parallel computer. Through our analysis and experimental results, we demonstrate that our algorithm substantially improves the state of the art in parallel direct solution of sparse linear systems—both in terms of scalability and overall performance. It is a well known fact that dense matrix factorization scales well and can be implemented efficiently on parallel computers. In this paper, we present the first algorithm to factor a wide class of sparse matrices (including those arising from two- and three-dimensional finite element problems) that is asymptotically as scalable as dense matrix factorization algorithms on a variety of parallel architectures. Our algorithm incurs less communication overhead and is more scalable than any previously known parallel formulation of sparse matrix factorization. Although, in this paper, we discuss Cholesky factorization of symmetric positive definite matrices, the algorithms can be adapted for solving sparse linear least squares problems and for Gaussian elimination of diagonally dominant matrices that are almost symmetric in structure. An implementation of our sparse Cholesky factorization algorithm delivers up to 20 GFlops on a Cray T3D for medium-size structural engineering and linear programming problems. To the best of our knowledge,
Multilevel Diffusion Schemes for Repartitioning of Adaptive Meshes.
For a large class of irregular mesh applications, the structure of the mesh changes from one phase of the computation  to the next. Eventually, as the mesh evolves, the adapted mesh has to be repartitioned to ensure good load  balance. If this new graph is partitioned from scratch, it may lead to an excessive migration of data among processors.  In this paper, we present schemes for computing repartitionings of adaptively refined meshes that perform diffusion of   
Parallel Multilevel Graph Partitioning.

Multilevel Graph Partitioning Schemes.
Abstract – In this paper we present experiments with a class of graph partitioning algorithms that reduce the size of the graph by collapsing vertices and edges, partition the smaller graph, and then uncoarsen it to construct a partition for the original graph. We investigate the effectiveness of many different choices for all three phases: coarsening, partition of the coarsest graph, and refinement. In particular, we present a new coarsening heuristic (called heavy-edge heuristic) for which the size of the partition of the coarse graph is within a small factor of the size of the final partition obtained after multilevel refinement. We also present a new scheme for refining during uncoarsening that is much faster than the Kernighan-Lin refinement. We test our scheme on a large number of graphs arising in various domains including finite element methods, linear programming, VLSI, and transportation. Our experiments show that our scheme consistently produces partitions that are better than those produced by spectral partitioning schemes in substantially smaller timer (10 to 35 times faster than multilevel spectral bisection). Also, when our scheme is used to compute fill reducing orderings for sparse matrices, it substantially outperforms the widely used multiple minimum degree algorithm. 1
A Highly Parallel Interior Point Algorithm.

Analysis of Multilevel Graph Partitioning.
Recently, a number of researchers have investigated a class of algorithms that are based on multilevel graph partitioning that have moderate computational complexity, and provide excellent graph partitions. However, there exists little theoretical analysis that could explain the ability of multilevel algorithms to produce good partitions. In this paper we present such an analysis. We show under certain reasonable assumptions that even if no refinement is used in the uncoarsening phase, a good bisection of the coarser graph is worse than a good bisection of the finer graph by at most a small factor. We also show that the size of a good vertex-separator of the coarse graph projected to the finer graph (without performing refinement in the uncoarsening phase) is higher than the size of a good vertexseparator of the finer graph by at most a small factor.
Introduction to Parallel Computing.

A parallel formulation of interior point algorithms.

Unstructured Tree Search on SIMD Parallel Computers.
In this paper, we present new methods for load balancing of unstructured tree computations on large-scale SIMD machines, and analyze the scalability of these and other existing schemes. An efficient formulation of tree search on a SIMD machine comprises of two major components: (i) a triggering mechanism, which determines when the search space redistribution must occur to balance search space over processors; and (ii) a scheme to redistribute the search space. We have devised a new redistribution mechanism and a new triggering mechanism. Either of these can be used in conjunction with triggering and redistribution mechanisms developed by other researchers. We analyze the scalability of these mechanisms, and verify the results experimentally. The analysis and experiments show that our new load balancing methods are highly scalable on SIMD architectures. Their scalability is shown to be no worse than that of the best load balancing schemes on MIMD architectures. We verify our theoretical...
Efficient Parallel Mappings of a Dynamic Programming Algorithm A Summary of Results.

Unstructured Tree Search on SIMD Parallel Computers A Summary of Results.

